package com.zxy.leetcode._00000_00099._00040_00049;

/**
 * https://leetcode-cn.com/problems/first-missing-positive/
 *
 * 缺失的第一个正数
 * 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
 *
 * 提示：
 * 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
 */
public class Test00041 {

    public static void main(String[] args) {
        Test00041 test = new Test00041();

        int[] nums = {-1, 4, 2, 1, 9, 10};
        System.out.println(test.firstMissingPositive(nums));
    }

    /*
    https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
    看了这个思路后进行解答

    https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
    官方有另一种解法方案
    把所有的负数置为不可能的结果，即length
    循环遍历，把对应值对应的排序位置进行取负（由于取负数，后面重新遍历的时候，可以知道原值，相当于打标且保留原值）
    循环遍历，找不出不在对应位置的数字
     */
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        for (int i=0; i<nums.length; i++) {
            int num = nums[i];
            int index = num - 1;
            if (num > 0 && index != i && index < nums.length && num < nums.length && nums[i] != nums[index]) {
                // num应该在index=num-1的位置上
                nums[i] = nums[index];
                nums[index] = num;
                // 换完之后，当前位置可能不正确了，需要再来一遍
                i --;
            }
        }

        int last = nums.length-1;
        int num = nums[last];
        if (num > 0 && num < last) {
            int index = num - 1;
            nums[last] = nums[num - 1];
            nums[index] = num;
        }

        for (int i=0; i<nums.length; i++) {
            if (nums[i] != i+1) {
                return i + 1;
            }
        }

        return nums.length + 1;
    }
}
